package personal.leil.learning.queen;

/**
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列、也不在同一条斜线上。
 * 给定一个整数n，返回n皇后的摆法有多少种。
 * n=1，返回1。
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0。
 * n=8，返回92。
 *
 * @author Leil
 * @version 1.0
 * @since 2024/1/29
 */
public class NQueen {

    /******* For Normal **********/
    public static int nQueenCalc(int n) {
        int[] record = new int[n];
        return process(0, record, n);
    }


    public static int process(int i, int[] record, int n) {
        if (i == n) {
            return 1;
        }
        int res = 0;
        // 在i行上遍历所有列，判断哪一列可以满足摆放皇后的条件，添加后递归的处理下一行
        for (int j = 0; j < n; j++) {
            if (isValid(i, j, record)) {
                record[i] = j;
                res += process(i + 1, record, n);
            }
        }
        return res;
    }

    private static boolean isValid(int i, int j, int[] record) {
        for (int k = 0; k < i; k++) {
            if (record[k] == j  // 共列
                    // 共斜线
                    || Math.abs(record[k] - j) == Math.abs(k - i)) {
                return false;
            }
        }
        return true;
    }

    /************ For Optimize ***************/
    public static int nQueenCalcOpt(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return processOpt(limit, 0, 0, 0);
    }

    /**
     * 利用二进制位代表Queen占位优化算法
     *
     * @param limit              每位都占满表示的二进制数
     * @param columnLimit        当前行列上限制（二进制位为1表示不能放Queen）
     * @param leftDiagonalLimit  当前行左斜线限制
     * @param rightDiagonalLimit 当前行右斜线限制
     * @return 方案的数量
     */
    public static int processOpt(int limit,
                                 int columnLimit,
                                 int leftDiagonalLimit,
                                 int rightDiagonalLimit) {
        if (limit == columnLimit) {
            return 1;
        }
        // 找出可以放Queen的位置（二进制位上为1表示可以放Queen）
        int pos = limit & (~(columnLimit | leftDiagonalLimit | rightDiagonalLimit));

        int res = 0;
        // 可以放Queen的位置从右往左依次尝试
        while (pos != 0) {
            // 取出最右侧的1
            int rightOne = pos & (~pos + 1);
            pos = pos - rightOne;
            res += processOpt(limit,
                    columnLimit | rightOne,
                    (leftDiagonalLimit | rightOne) << 1,
                    (rightDiagonalLimit | rightOne) >> 1);
        }
        return res;
    }


    /*************************** For Test *********************************/
    public static void main(String[] args) {
        long t1 = System.currentTimeMillis();
        int result = nQueenCalc(14);
        long t2 = System.currentTimeMillis();
        System.out.println("Result for NQueen : " + result + " for time : " + (t2 - t1));

        long t3 = System.currentTimeMillis();
        int result1 = nQueenCalcOpt(14);
        long t4 = System.currentTimeMillis();
        System.out.println("Result for NQueen Calculate : " + result1 + " for time : " + (t4 - t3));
    }

}
